Transport Layer Security (TLS) and its predecessor, Secure Sockets Layer (SSL), are cryptographic protocols that provide security and data integrity for communications over networks such as the Internet. A communication session over TLS or SSL has two distinct phases. In the first phase, a client and a server set up a shared secret key and perform authentication. (Normally, authentication is one-way—i.e., the client authenticates the server, but not vice versa—although TLS and SSL also support two-way authentication.) In the second phase, the shared secret key is used to encrypt and/or authenticate data that is transmitted between the client and server.
Normally, agreement on the shared secret between the client and the server is performed, during the first phase, by the following procedure. After the client and server exchange initial “hello” messages, the server sends its certificated public key to the client. The client then chooses a value, x, and uses the server's public key to encrypt a message that contains x. The server then uses its private key to decrypt the message and to recover x from the message. Once the server and client both have knowledge of x, either they use x as the shared secret key, or they derive the shared secret key from x using an algorithm that is known to both the client and the server.
A problem that arises in this key agreement procedure is that the procedure involves decryption, by the server, of the message that contains x. TLS/SSL supports many cipher suits that can use a variety of different encryption/decryption techniques. (The cipher suite is agreed to between the client and server as part of their “hello” messages, before the key agreement part of the first phase takes place.) However, in a typical TLS/SSL communication, the chosen cipher suite uses Rivest-Shamir-Adelman (“RSA”) public key encryption to perform key agreement. RSA encryption can be performed relatively efficiently, but RSA decryption is computationally expensive. Thus, for every TLS/SSL connection, the server has to perform an expensive RSA decryption. If the server processes hundreds or thousands of connections per minute, key agreement that involves RSA decryption can create a bottleneck on the server. Many servers use a significant portion of their available processing capacity doing RSA decryption as part of the key agreement protocol.